package algorthm.systemTraning.binaryTree;
import java.util.ArrayList;
public class ISBST{

	public static void main(String[] args){
		int maxLevel = 4;
		int maxValue = 100;
		int testTimes = 1000000;
		for (int i = 0; i < testTimes; i++) {
			Node head = generateRandomBST(maxLevel, maxValue);
			if (isBST1(head) != isBST(head)) {
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");
	
	}
	public static boolean isBST1(Node head) {
		if (head == null) {
			return true;
		}
		ArrayList<Node> arr = new ArrayList<>();
		in(head, arr);
		for (int i = 1; i < arr.size(); i++) {
			if (arr.get(i).value <= arr.get(i - 1).value) {
				return false;
			}
		}
		return true;
	}

	public static void in(Node head, ArrayList<Node> arr) {
		if (head == null) {
			return;
		}
		in(head.left, arr);
		arr.add(head);
		in(head.right, arr);
	}

	public static boolean isBST(Node head){
		if(null == head) return true ;

        Info info = process(head);

		if(null != info){
		   return info.isBST ;
		}
	    return false;
	}
	public static Info process(Node head){
	
		if(null == head) return null ;
		Info Linfo = process(head.left);
		Info Rinfo = process(head.right);
	    int max = head.value ;
	    int min = head.value ;
		if(null != Linfo && Linfo.max > max ){
		  max = Linfo.max ;
		}
		
		if(null != Rinfo && Rinfo.max > max ){
		  max = Rinfo.max ;
		}

		if(null != Linfo && Linfo.min < min ){
		  min = Linfo.min ;
		}
		if(null != Rinfo && Rinfo.min < min){
		  min = Rinfo.min ;
		}
		/* Info 的设计中取了左孩子的最大值，右孩子的最小值，
		 这样设计就是要从否定判断角度来判断左右孩子是否是平衡二叉树。
		 所以先设 isBST 为 true ，然后再列举出它不是的情况。
        */
		boolean isBST = true ;
		if(null != Linfo && !Linfo.isBST){
			isBST = false ;
		
		}
		if(null != Rinfo && !Rinfo.isBST){
			isBST = false ;
		
		}
		if(null != Rinfo && Rinfo.min <= head.value ){
	           isBST = false ;	
		}
		if(null != Linfo && Linfo.max >= head.value ){
	           isBST = false ;	
		}
		return new Info(isBST , max , min);
	
	} 
	public static class Node{
		public int value ;
		public Node left ;
		public Node right;
		public Node(int value){
			this.value = value ;
		}
	
	}
	public static class Info{
		public boolean isBST ;	
		public int max;	
		public int min;
		public Info(boolean isBST , int max , int min){
			this.isBST = isBST;  
			this.max = max ;
			this.min = min ;
		}
	
	}
	// for test
	public static Node generateRandomBST(int maxLevel, int maxValue) {
		return generate(1, maxLevel, maxValue);
	}

	// for test
	public static Node generate(int level, int maxLevel, int maxValue) {
		if (level > maxLevel || Math.random() < 0.5) {
			return null;
		}
		Node head = new Node((int) (Math.random() * maxValue));
		head.left = generate(level + 1, maxLevel, maxValue);
		head.right = generate(level + 1, maxLevel, maxValue);
		return head;
	}	

}

